import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/22 21:59
 * @description 涉及到排列问题，大多数都可以用回溯完成，实在不行就记忆化回溯
 */
public class Solution {
    public static void main(String[] args) {

    }

    List<Integer>[] match;
    boolean[] vis;
    int num;
    public int countArrangement(int n) {
        vis = new boolean[n + 1];
        match = new List[n + 1];
        for (int i = 1; i <= n; i++) {
            match[i] = new ArrayList<>();
        }
        // 预处理每个位置下能够选择的数字
        for (int i = 1; i <= n ; i++) {
            for (int j = 1; j <= n; j++) {
                if (i % j == 0 || j % i == 0) {
                    match[i].add(j);
                }
            }
        }
        backtrack(1, n);
        return num;
    }

    private void backtrack(int i, int n) {
        if (i == n + 1) {
            num++;
            return;
        }
        for (int x : match[i]) {
            if (!vis[x]) {
                vis[x] = true;
                backtrack(i + 1, n);
                vis[x] = false;
            }
        }
    }
}
